1. Field of the Invention
The present invention is directed to a mechanism for filtering production rules which expresses conditions to be satisfied, and for identifying during successive inference cycles rules whose conditions are satisfied for deduced facts. The mechanism includes a sorting system for ordering the conditions of the rules according to a sorting criterion in order to verify the conditions of the rules on the basis of an order in which the conditions are to be applied.
2. Description of the Related Art
A filter mechanism of this general kind is disclosed in the document TSI Vol. 5 N.degree. 3, Jun. 1986, "Un langage declaratif: SNARK", J. L. Lauriere. This type of filter mechanism is designed primarily for computerized systems to assist in decision making, often referred to as an expert system. An expert system conventionally includes three parts, namely, a first working memory or fact base containing deduced facts, a second working memory or knowledge base containing a set of production rules each expressing one or more conditions to be satisfied in relation to one or more conclusions to be deduced, and a deduction procedure or inference engine.
Expert systems are widely used in industry, their applications including diagnosing malfunctions of an installation.
The deduction procedure is usually arranged to effect an inference cycle in three stages: filtering, resolution of conflict and inference. The filter stage entails determining the production rules whose conditions are satisfied for facts in the fact base. The conflict resolution stage entails selecting rules from the rules declared as candidates by the filter stage. The inference stage entails adding facts to, removing facts from or modifying facts in the fact base according to the conclusion(s) of the rules retained in the conflict resolution stage.
The efficacy of the filter stage has a decisive influence on the efficacy of the deduction process as it frequently uses more than 80% of the total processing time for each inference cycle.
In the above-mentioned document, the deduction procedure includes a production rule filtering mechanism including a sorting system for ordering the conditions of the rules according to a sorting criterion in order to verify the conditions of the rules on the basis of an order in which the conditions are to be applied. The sorting criterion considers the condition to be applied first, for a given rule, is that which is least often satisfied for the deduced facts. The ordering of the conditions of the rules reduces the processing time needed for the filter stage. This known filter mechanism activates the sorting system on each inference cycle. As a result a filter mechanism of this kind consumes a lot of processing time because the sorting system is itself a large consumer of processing time. Moreover, it has been determined that in 99% of inference cycles the sorting system orders the conditions of the rules in the same order (in which they are to be applied) as in the preceding cycle, because the deduced facts do not change greatly between two consecutive inference cycles. There is therefore no utility in activating the sorting system for each inference cycle. An object of the invention is to remedy this drawback.
Another filter mechanism is disclosed in the document AAAI, National Conference On Artificial Intelligence, 1987, "TREAT: a better match algorithm for AI production systems", D. P. Miranker. This filter mechanism uses a representation of the conditions of the production rules in the form of a discrimination network in which each node represents a condition model of one or more production rules. A discrimination network of this kind is particularly advantageous when the conditions of the rules contain common variables. When a condition contains n variables, the node of the network corresponding to this condition memorizes the values of the sets of n facts in the fact base which satisfy the condition. The arcs of the discrimination network represent the conjunctions defined between the conditions of the rules when writing the production rules. To determine the production rules for which all the conditions are satisfied by the facts in the fact base, the filter mechanism establishes successive conjunctions between the sets of n values memorized in the nodes of the discrimination network. The filter mechanism known from the aforementioned document includes a sorting system which partially orders the nodes in the discrimination network. This sorting system is such that, during a current inference cycle, the conjunction stage for two nodes of the discrimination network corresponding to two conditions of a production rule starts at the node corresponding to the condition implied by a new fact deduced during the inference cycle immediately preceding the current inference cycle. The order in which the nodes of the network corresponding to the other conditions of the rule are applied is exactly the same as that defined when the rule was written. It has been found that the processing time needed to make the conjunctions depends on the order in which the conjunctions between network nodes are made. This processing time can be very substantially reduced if the order of taking account of the nodes is calculated quickly for all the nodes to which the conjunction stage is relevant. Another object of the invention is to improve a filter mechanism of this kind.